//未优化版本
#include <iostream>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
PII q[N];  //开个数组来存质因数以及其指数
int t = 0; //记录现阶段数组中的元素个数
int n, m;  //获取输入

void quick_sort(PII q[], int l, int r)
{
    if (l >= r)
        return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1].first;
    while (i < j)
    {
        do
            i++;
        while (q[i].first < x);
        do
            j--;
        while (q[j].first > x);
        if (i < j)
            swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
    return;
}

int main()
{
    cin >> m;
    while (m--)
    {
        t = 0;
        cin >> n;
        for (int i = 2; i <= n; ++i)
        {
            if (n % i == 0)
            {
                q[t].first = i;
                q[t].second = 0;
                while (n % i == 0)
                {
                    n /= i;
                    q[t].second++;
                }
                t++;
            }
        }
        //quick_sort(q, 0, t - 1);
        for (int i = 0; i < t; ++i)
            cout << q[i].first << " " << q[i].second << endl;
        cout << endl;
    }
    return 0;
}

//优化版本，由于身就是从小到大遍历而来，所以不用排序，直接输出即可
#include <iostream>
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
PII q[N];  //开个数组来存质因数以及其指数
int t = 0; //记录现阶段数组中的元素个数
int n, m;  //获取输入

// void quick_sort(PII q[], int l, int r)
// {
//     if (l >= r)
//         return;
//     int i = l - 1, j = r + 1, x = q[l + r >> 1].first;
//     while (i < j)
//     {
//         do
//             i++;
//         while (q[i].first < x);
//         do
//             j--;
//         while (q[j].first > x);
//         if (i < j)
//             swap(q[i], q[j]);
//     }
//     quick_sort(q, l, j), quick_sort(q, j + 1, r);
//     return;
// }

int main()
{
    cin >> m;
    while (m--)
    {
        t = 0;
        cin >> n;
        for (int i = 2; i <= n / i; ++i)
        {
            if (n % i == 0)
            {
                q[t].first = i;
                q[t].second = 0;
                while (n % i == 0)
                {
                    n /= i;
                    q[t].second++;
                }
                t++;
            }
        }
        if (n > 1)
            q[t].first = n, q[t++].second = 1;
        //quick_sort(q, 0, t - 1);
        for (int i = 0; i < t; ++i)
            cout << q[i].first << " " << q[i].second << endl;
        cout << endl;
    }
    return 0;
}